package com.bo.day20231221;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * <p>
 * 1）把链表放入数组里，在数组上做partition（笔试用）
 * <p>
 * 2）分成小、中、大三部分，再把各个部分之间串起来（面试用）
 * 实现思路：
 * 6个指针：
 * 小于开始指针：指向小于开始的位置
 * 小于结束指针：指向小于结束的位置,一指下去
 * 等于开始指针
 * 等于结束指针
 * 大于开始指针
 * 大于结束指针
 * 最后：小于结束的指针->等于开始指针->等于结束指针->大于开始指针
 *
 * @Author: gpb
 * @Date: 2023/12/22 9:58
 * @Description:
 */
public class SmallerEqualBigger {

    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);
        // head1 = listPartition1(head1, 4);
        head1 = listPartition(head1, 5);
        printLinkedList(head1);

    }

    public static void test (String[] args) {
        Node node = new Node(3);
        node.next = new Node(1);
        node.next.next = new Node(5);
        node.next.next.next = new Node(8);
        node.next.next.next.next = new Node(2);

        Node smallerBegin = null;
        Node smallerEnd = null;
        while (node != null) {
            if (node.value < 3) {
                if (smallerBegin == null) {
                    smallerBegin = node;
                    smallerEnd = node;
                } else {
                    smallerEnd.next = node;
                    smallerEnd = smallerEnd.next;
                }
            }
            node = node.next;
        }
        System.out.println(smallerEnd.value);
    }

    public static class Node {
        public int value;
        public Node next;

        public Node (int data) {
            this.value = data;
        }
    }



    public static Node listPartition (Node head, int pivot) {
        if (head == null) {
            return null;
        }
        Node smallerBegin = null;
        Node smallerEnd = null;
        Node equalBegin = null;
        Node equalEnd = null;
        Node biggerBegin = null;
        Node biggerEnd = null;
        Node next = null;
        while (head != null) {
            //  连接节点的时候确保只有一个节点
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (smallerBegin == null) {
                    smallerBegin = head;
                    smallerEnd = head;
                } else {
                    // 和结束指针连接
                    smallerEnd.next = head;
                    // 结束指针往后移动
                    smallerEnd = head;
                }
            }
            if (head.value == pivot) {
                if (equalBegin == null) {
                    equalBegin = head;
                    equalEnd = head;
                } else {
                    // 和结束指针连接
                    equalEnd.next = head;
                    // 结束指针往后移动
                    equalEnd = head;
                }
            }
            if (head.value > pivot) {
                if (biggerBegin == null) {
                    biggerBegin = head;
                    biggerEnd = head;
                } else {
                    // 和结束指针连接
                    biggerEnd.next = head;
                    // 结束指针往后移动
                    biggerEnd = head;
                }
            }
            head = next;
        }
        // 小于区域的尾巴,连接等于区域的头,等于区域的尾巴连接大于区域的头
        if (smallerEnd != null) {
            smallerEnd.next = equalBegin;
            // 谁去连接大于区域的头,谁变成 等于去的尾巴
            equalEnd = equalEnd == null ? smallerEnd : equalEnd;
        }
        // 一定是需要用 等于区域的尾巴去连接头
        // 有等于区域,equalEnd -> 等于区域的尾巴节点
        // 无等于区域,equalEnd -> 小于区域的尾巴节点
        if (equalEnd != null) {
            equalEnd.next = biggerBegin;
        }
        return smallerBegin != null ? smallerBegin : (equalBegin != null ? equalBegin : biggerBegin);
    }
    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

}
